class Solution {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
    //106. 从中序与后序遍历序列构造二叉树
    public int postIndex = 0;
    public TreeNode buildTree1(int[] inorder, int[] postorder){
     postIndex = postorder.length - 1;
    return buildTreeChild1(inorder, postorder, 0, inorder.length-1);
     }
    public TreeNode buildTreeChild1(int[] inorder, int[] postorder,
                                   int begin, int inend) {
        if (begin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postIndex]);
        int rootIndex = finfIndex(inorder, begin, inend, postorder[postIndex]);
        postIndex--;
        if (rootIndex == -1) {
            return null;
        }
        root.right = buildTreeChild(inorder, postorder, rootIndex + 1, inend);
        root.left = buildTreeChild(inorder, postorder, begin, rootIndex - 1);
        return root;
    }
    protected int finfIndex(int[] inorder,
                            int begin, int inend, int vla) {
        for (int i = begin; i <= inend; i++) {
            if (inorder[i] == vla) {
                return i;
            }
        }
        return -1;
    }
    //105. 从前序与中序遍历序列构造二叉树
    public int preIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeChild(preorder, inorder, 0, inorder.length - 1);
    }

    public TreeNode buildTreeChild(int[] preorder, int[]
            inorder, int begin, int inend) {
        if (begin > inend) {
            return null;
        }
        TreeNode root = new TreeNode(preorder[preIndex]);
        int rootIndex = findIndex(inorder, begin, inend, preorder[preIndex]);
        preIndex++;
        if (rootIndex == -1) {
            return null;
        }
        root.left = buildTreeChild(preorder, inorder, begin, rootIndex - 1);
        root.right = buildTreeChild(preorder, inorder, rootIndex + 1, inend);
        return root;
    }
    public int findIndex(int[] inorder, int begin, int inend, int val) {
        for (int i = begin; i <= inend; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }
    //606. 根据二叉树创建字符串
    public String tree2str(TreeNode root) {
        StringBuffer stringBuffer=new StringBuffer();
        tree2strChild(root,stringBuffer);
        return stringBuffer.toString();
    }
    public void tree2strChild(TreeNode root,StringBuffer stringBuffer){
        if(root==null){
            return ;
        }//root不为空。添加到StringBuffer
        stringBuffer.append(root.val);
        if(root.left!=null){//左不为空，添加左括号
            stringBuffer.append('(');
           tree2strChild(root.left,stringBuffer);
            stringBuffer.append(')');
        }else{
            if(root.right==null){//右为空，直接返回
                return ;
            }else{//左为空，右不为空，添加“()"
               stringBuffer.append("()");
            }
        }
        if(root.right==null){
            return;
        }
        stringBuffer.append('(');
        stringBuffer.append(root.right.val);
        stringBuffer.append(')');
    }
}
